function merge(left: number[], right: number[]): number[] {
  let result = [];
  let i = 0,j = 0;
  while (i < left.length && j < right.length) {
    if (left[i] <= right[j]) {
      result.push(left[i++]);
    } else {
      result.push(right[j++]);
    }
  }
  // 如果left或right数组为空 就把另外一个的剩余数组合并；
  if (i < left.length) {
    result.push(...left.slice(i))
  } else {
    result.push(...right.slice(j))
  }
  return result;
}
export default function mergeSort(arr: number[]): number[] {
  if (arr.length < 2) return arr;
  let mIndex = Math.floor(arr.length / 2);
  let leftArr = mergeSort(arr.slice(0, mIndex));
  let rightArr = mergeSort(arr.slice(mIndex));
  return merge(leftArr, rightArr);
}
